package com.huangyi;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        //太平洋大西洋水流问题
        class Solution {
            int m, n;
            int[] dx = {1, -1, 0, 0};
            int[] dy = {0, 0, 1, -1};
            boolean[][] visP;  // 可流入太平洋的标记
            boolean[][] visA;  // 可流入大西洋的标记

            public List<List<Integer>> pacificAtlantic(int[][] heights) {
                m = heights.length;
                n = heights[0].length;
                visA = new boolean[m][n];
                visP = new boolean[m][n];

                // 从太平洋边界开始 DFS（左边和上边）
                for(int i = 0; i < m; i++){
                    dfsP(heights, i, 0);  // 左边界
                }
                for(int j = 0; j < n; j++){
                    dfsP(heights, 0, j);  // 上边界
                }

                // 从大西洋边界开始 DFS（右边和下边）
                for(int i = 0; i < m; i++){
                    dfsA(heights, i, n - 1);  // 右边界
                }
                for(int j = 0; j < n; j++){
                    dfsA(heights, m - 1, j);  // 下边界
                }

                // 收集同时可达两个海洋的格子
                List<List<Integer>> result = new ArrayList<>();
                for(int i = 0; i < m; i++){
                    for(int j = 0; j < n; j++){
                        if(visP[i][j] && visA[i][j]){
                            result.add(Arrays.asList(i, j));
                        }
                    }
                }
                return result;
            }

            // 从大西洋逆流而上的 DFS
            public void dfsA(int[][] heights, int si, int sj){
                visA[si][sj] = true;
                for(int i = 0; i < 4; i++){
                    int x = si + dx[i], y = sj + dy[i];
                    // 逆流条件：下一个格子高度 >= 当前格子（水能从高处流下来）
                    if(x >= 0 && x < m && y >= 0 && y < n && !visA[x][y] && heights[x][y] >= heights[si][sj]){
                        dfsA(heights, x, y);
                    }
                }
            }

            // 从太平洋逆流而上的 DFS
            public void dfsP(int[][] heights, int si, int sj){
                visP[si][sj] = true;
                for(int i = 0; i < 4; i++){
                    int x = si + dx[i], y = sj + dy[i];
                    // 逆流条件：下一个格子高度 >= 当前格子
                    if(x >= 0 && x < m && y >= 0 && y < n && !visP[x][y] && heights[x][y] >= heights[si][sj]){
                        dfsP(heights, x, y);
                    }
                }
            }
        }

        //扫雷游戏
        class Solution2 {
            int[] dx = {0, 0, 1, -1, -1, -1, 1, 1};
            int[] dy = {1, -1, 0, 0, -1, 1, -1, 1};
            int m, n;

            public char[][] updateBoard(char[][] board, int[] click) {
                m = board.length;
                n = board[0].length;
                dfs(board, click[0], click[1]);
                return board;
            }

            public void dfs(char[][] board, int si, int sj){
                // 规则1：点到地雷，游戏结束
                if(board[si][sj] == 'M'){
                    board[si][sj] = 'X';
                    return;
                }

                // 统计周围8个方向的地雷数量
                int cur = 0;
                for(int i = 0; i < 8; i++){
                    int x = si + dx[i], y = sj + dy[i];
                    if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M'){
                        cur++;
                    }
                }

                // 规则3：周围有地雷，标记数字
                if(cur > 0){
                    board[si][sj] = (char)(cur + '0');
                }
                // 规则2：周围无地雷，递归展开
                else{
                    board[si][sj] = 'B';
                    for(int i = 0; i < 8; i++){
                        int x = si + dx[i], y = sj + dy[i];
                        // 只递归处理未挖出的空方块
                        if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E'){
                            dfs(board, x, y);
                        }
                    }
                }
            }
        }
    }
}